#include "iostream"
using namespace std;

// lowbit 返回 x 的二进制表示中最低位的 1 所对应的值
int lowbit(int x) {
    return x & (-x);
}

const int N = 1000;
int tree[N] = {0};

// m = lowbit(x), tree[x] = a[x] 和它前面共m个数相加的结果
// tree[x] = a[x] + a[x-1] + ... + a[x-(m-1)]
// 比如 tree[6] = a[6] + a[5]

// 单点修改： 修改元素 a[x], a[x] += d
void update(int x, int d) {
    while (x < N) {
        tree[x] += d;
        x += lowbit(x);
    }
}

// 区间查询： 查询区间 [1, x] 的和
int sum(int x) {
    int res = 0;
    while (x) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

// a[0] 不用
int a[11] = {0,4,5,6,7,8,9,10,11,12,13};

int main() {
    // 建树： 对每一个点都进行单点修改
        for (int i = 1; i <= 10; i++) {
                update(i, a[i]);
        }
        // 查询区间[5,8]的和
        cout << "old: [5,8]" << sum(8) - sum(4) << endl;
        // 一次修改 a[5] += 100
        update(5, 100);
        // 查询区间[5,8]的和
        cout << "new: [5,8]" << sum(8) - sum(4) << endl;
        return 0;
}